#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h> 
#include <string.h>
#include <fcntl.h>
#include <stdlib.h>
#include "makeargv.h"

#define MAX_NODES 100

#define INELIGIBLE 0
#define READY 1
#define RUNNING 2
#define FINISHED 3

typedef struct node {
   int id;
   char prog[1024];
   char input[1024];
   char output[1024];
   int children[10];
   int num_children;
   int status;
   pid_t pid;
} node_t;

int parseGraphFile(char *filename, node_t *n);
int parseInputLine(char *s, int id, node_t *n);
int determineReady(node_t *n, int num);
void execNodes(node_t *n, int num);
void fork_and_exec(node_t *n);
void waitForOneToFinish(node_t *n, int num);

int parseGraphFile(char *filename, node_t *n) {
   FILE *f;
   char buf[1024];
   int id = 0;
   if ((f = fopen(filename,"r")) == NULL) {
      perror("Couldn't open graph file for reading");
      exit(0);
   }

   while (fgets(buf,1024,f) != NULL) { // read one line from file
      strtok(buf,"\n"); // chop off trailing newline character
      if (parseInputLine(buf,id,n) > 0) { // parse it, modify node n
        n++; // next node after n (only if line is not blank)
        id++;
      }
   }
   fclose(f);
   return id;
}

int parseInputLine(char *s, int id, node_t *n) {

   char **strings;
   char **child_list;
   int c = 0;
   if (makeargv(s,":",&strings) == 0) { // chop it at every : char
      return 0; // if makeargv didnt do anything
   }

   makeargv(strings[1]," ",&child_list);

   strcpy(n->prog,strings[0]);
   strcpy(n->input,strings[2]);
   strcpy(n->output,strings[3]);
   n->id = id;
   n->num_children = 0;
   while (child_list[c] != NULL && strcmp(child_list[c],"none")!=0) {
      n->children[c] = atoi(child_list[c]);
      n->num_children++;
      c++;
   }
   return 1;
}

int determineReady(node_t *n, int num) {
   int eligible[MAX_NODES];
   int i,j;
   int marked = 0;
   int notdone = 0;
   for (i=0; i<num; i++)
      eligible[i] = 1; // assume everyone is eligible

   for (i=0; i<num; i++) {
      if (n[i].status != FINISHED) {
         for (j=0; j<n[i].num_children; j++)
            eligible[n[i].children[j]] = 0;
      }
   }

   for (i=0; i<num; i++) {
      if (eligible[i] && n[i].status == INELIGIBLE) {
         n[i].status = READY; // mark this node as ready-to-run!
         marked++;
      } else if (n[i].status != FINISHED) {
         notdone = 1;
      }
   }

   if (marked == 0 && notdone == 0)
      return -1; // return -1 when everyone is FINISHED

   return marked;

}

void execNodes(node_t *n, int num) {
   int i;
   for (i=0; i<num; i++) {
      if (n[i].status == READY) {
         fork_and_exec(n+i);
         n[i].status = RUNNING;
      }
   }
}

void fork_and_exec(node_t *n) {

   pid_t pid;

   pid = fork();

   if (pid == 0) { // child
      int input_file = open(n->input,O_RDONLY);
      if (input_file < 0) {
         perror("error opening input file in child after fork");
         exit(0);
      } else {
         dup2(input_file,STDIN_FILENO);
         close(input_file);
      }
      int output_file = open(n->output,O_WRONLY|O_CREAT|O_TRUNC,0644);
      if (output_file < 0) {
         perror("error opening output file in child after fork");
         exit(0);
      } else {
         dup2(output_file,STDOUT_FILENO);
         close(output_file);
      }

      char **prog_args;
      makeargv(n->prog," ",&prog_args);

      execvp(prog_args[0],prog_args);

      perror("exec error"); // never should get to this point if exec worked
      exit(0);

   } else if (pid > 0) {
      // parent records PID of this guy
      n->pid = pid;
      printf("started [%s] with PID [%d]\n",n->prog,pid);
      // already marked as RUNNING by execNodes()
   } else {
      perror("fork error");
   }
}

void waitForOneToFinish(node_t *n, int num) {

   pid_t p;
   int i;

   p = wait(NULL);

   for (i=0; i<num; i++) {
      if (n[i].status == RUNNING && n[i].pid == p) {
         n[i].status = FINISHED;
      }
   }
}

int main(int argc, char **argv) {

   node_t mainnodes[MAX_NODES];

   if (argc != 2) {
      printf("usage: %s graph-file\n",argv[0]);
      return -1;
   }

   int num = parseGraphFile(argv[1],mainnodes);

   while (determineReady(mainnodes,num) >= 0) {

      execNodes(mainnodes,num);
      waitForOneToFinish(mainnodes,num);

   }

   return 0;

}
